1. Field of the Invention
The present invention relates in general to a system and a method for analyzing the static timing for LSIs and more particularly to a system and a method for analyzing the static timing for searching circuits for their critical paths based on the information of transistor connections.
2. Description of the Prior Art
Recently the number of transistors merged in an LSI has drastically increased, accompanied by the ever increasing complexity of the circuits of logic LSIs represented by, in particular, microprocessors. Presently, to design and manufacture semiconductor devices, it is indispensable to employ CAD systems, which help improve the circuit performance and reduce the time required to fabricate them. To achieve this purpose is available such a static-timing analysis technique as PathMill, which searches circuits for their critical paths based on the transistor-connection information. This static-timing analysis technique has rapidly pervaded the industry because it is speedy in analysis and does not require combinational strings (hereinafter called test vectors) of input signals. This technique is proposed for use in various types of static-timing analysis systems such as those which analyze the circuits for each inverter, NAND gate, and other gate and those which do so for each transistor. Moreover, various types of algorithms are proposed for searching for the paths. Various types of algorithms are also available for use in the per-transistor basis static-timing analysis technique. FIG. 1 shows an example of flowchart for processing executed by a conventional static-timing analysis system. This per-transistor basis static-timing analysis system searches for, based on the transistor-connection information, the paths having the largest delay out of those which the signals come from or go out.
First, the analysis system reads in a net list to construct an internal data structure (step S1). To carry out a per-transistor basis analysis, the system generally expands the hierarchical structure, thus providing an overall flat condition. Next, according to the rules described later, the analysis system narrows down the transistor signal-flow directions (step S2). This enables the efficient performing of the subsequent path search. Then, the analysis system, based on the clock-signal nodes specified by the user, divides all the sequential circuits into blocks of the circuits composed of only combinational sub-circuits (step S3). The subsequent processes are all carried out for each of those blocks. Then, the paths are searched for (step S4). The system first searches for paths as assuming one of the incoming signals to be a high-to-low changing signal and then does so as assuming it to be a low-to-high changing signal, thus finding the possible longest paths. The system repeats this process for each of the other incoming signals, to find the critical paths of a desired circuit. The paths can thus be searched for by repeating a process of assumption and verification for the signal flow to trace the propagation of the signal. When having completed the process of path searching for all the blocks (step S5), the system outputs the results (step S6).
Step S2 mentioned earlier for the narrowing down of transistor signal flow directions is described as follows. A MOS transistor, originally a four-terminal element, is thought of as a three-terminal element in which the substrate terminal is generally ignored in the static-timing analysis method. Assume here that in an NMOS transistor shown in FIG. 2(a) a logically positive value (power supply potential) is applied to the terminal G and the terminal D is connected to a grounded capacitor so that a current I would flow from the terminal D through the terminal S if the terminal S is grounded. This condition is here defined as a state where, as shown in FIG. 2(a), a low-level signal is propagated from the terminal S through the terminal D. Likewise, if, in a PMOS transistor shown in FIG. 2(d), the terminal G is grounded and the terminal D is connected to a grounded capacitor, a current I would flow from the terminal S through the terminal D when a logically positive value (power-supply potential) is applied to the terminal S. This condition is defined as a state where, as shown in FIG. 2(d), a high-level signal is propagated from the terminal S through the terminal D. Likewise, as shown in FIGS. 2(b) and 2(c), the signal flow directions through the PMOS and NMOS transistors respectively are determined. Originally, it cannot be known in which directions of the source and drain terminals the signal flows in MOS transistors; however, when either one of these two terminals is grounded or connected to a power-supply potential, the direction in which the signal flows through the transistor is limited to one.
In the case where, as shown in FIG. 2(e), an incoming signal indicated by IN is connected to the source terminal of the NMOS transistor, this signal can only either be a high level (connected to the power-supply potential) or a low level (grounded), so that the signal flow is limited in the arrow direction shown in the figure. Likewise, in the case of the PMOS transistor such as shown in FIG. 2(f), the signal flow is limited in the arrow direction in the figure. Also in the case of the NMOS transistor such as shown in FIG. 2(g), in which it cannot be known in which direction a signal would flow at its terminal S, when the same signal comes from all portions connected thereto, the signal flow can be limited in the arrow direction shown in the figure. Likewise, in the case of the PMOS transistor such as shown in FIG. 2(h) also, the signal-flow direction can be limited.
By utilizing those rules, it is possible to narrow down the signal-flow directions for those transistors which are connected to the transistor whose direction is already narrowed down.
Next, at the step S3 where a sequential circuit is divided into a number of blocks, the sequential circuit is actually divided into a number of combinational-circuit blocks if possible.
Then, the algorithm for the path search step S4 is described as follows. As mentioned earlier, this step searches the circuit from the arrival of a particular incoming signal considered to have changed from a high state to a low state through its leaving as an outgoing signal for the possible longest path from the viewpoint of circuit operations. The system carries out this type of search operation for each incoming signal in both cases where it has changed from a high state to a low state and vice versa, to find the longest path from among those searched at this step.
Note that generally every transistor in a circuit is taken to be a linear resistor, in calculation of the propagation delay time, so that its apparent resistance may be multiplied by a stray capacitance in approximation to the RC product as a time constant, and the description of how to do so is omitted here. The following description does not cover details of delay time calculation, assuming that each inter-node delay is already calculated.
The path search operation concerns two states of each node: the one before change and the other after it. The state before change refers to the one before the incoming signal changes and the state after change, the one after the changed input signal has influenced all the elements of a particular circuit.
Assume here that such a state is propagated from one ode to the next one. Such a situation is called a sequential search. Even this single assumption premises several new assumptions as necessary conditions. Here, the condition for nodes required to be directly influenced by a changed node is called a direct condition. Also, the condition for a particular node required to establish its own direct condition so that all the transistors connected thereto are taken into account is called an indirect condition. Such a change in state of a node shifts to its adjacent one. Thus one assumption gives birth to several new assumptions, each of which then produces different new assumptions, so that the assumption pervades the adjacent nodes one by one. The system continues this assumption until it reaches a node which has a power supply, ground, incoming signal, outgoing signal, or other special attribute or a node beyond which the sequential search is no longer possible, thus deciding whether the assumption is true or false. When an assumption is decided to be false, i.e. is denied, the system returns to that denial point in time to correct both that assumption and the dependent ones. Thus, each of the direct and indirect conditions needs to be traced back until its own assumption is confirmed to be true. This operation is called a backward search. Thus, the system repeats a forward search, to cover the paths of each signal from its entering through leaving.
In such a way as described above, the system stores paths thus obtained for each block and does it store the path having the largest delay in a file or displays on a CRT screen.
If, in this process, the transistor signal flow is properly directed, a conflict in a particular assumption of path search would ignore a smaller number of assumptions accumulated theretofore than otherwise. This enables reducing the time for processing. Also, an appropriate directing of the transistor signal flow would also decrease the number of false paths, i.e. those paths which are impossible from the viewpoint of circuit operations, because of an accumulation of false assumptions.
A prior art is described below based on the analysis of a test circuit prepared for evaluation.
Here, how to analyze a circuit conventionally called a barrel shifter is described. The barrel shifter will execute shift operations at a high speed in microprocessors etc. FIG. 3 shows a portion of the barrel shifter circuit. As shown in the figure, the barrel shifter employs a lot of transmission gates.
First the processing directs, based on the above-mentioned rules, the signal flow only for the transistors that make up the inverter and not for those transistors that make up the transmission gate.
Therefore, the path-search process would search for such a path as indicated by a broken-line arrow in FIG. 3, i.e. a path which is impossible circuit operation-wise, the verification of which may greatly elongate the processing or may output false paths.
Next, FIG. 4 shows a flowchart for the prior art. This example, instead of narrowing down the transistor signal-flow directions, carries out pattern matching to converts path search from a per-transistor basis to a per-gate basis. There are various types of pattern matching techniques available, but their description is omitted here.
Those techniques, however, cannot determine the direction in which the transmission gate signal such as shown in FIG. 3 would flow and therefore may give false paths or greatly increase the processing time as mentioned above.
As can be seen from this, the prior art suffers from a poor ratio of determining the direction in which the transistor signal would flow in such a circuit as having a lot of path transistors, so that a lot of false paths will be given in the analysis results accompanied by a greatly long processing time.